package pprg.quicksort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class QuickSort {

	private static int threshold;
	private static List<Thread> threads = Collections.synchronizedList(new ArrayList<Thread>());
	
	public static void quicksort(int[] a, int leftIndex, int rightIndex) {
		if (leftIndex < rightIndex) {
			int i = partition(a, leftIndex, rightIndex);
			quicksort(a, leftIndex, i - 1);
			quicksort(a, i, rightIndex);
		}
	}

	public static void sequentialQuicksort(int[] a) {
		quicksort(a, 0, a.length - 1);
	}

	public static void parallelQuicksort(int[] a, int threshold) {
		setThreshold(threshold);
		threads = new ArrayList<Thread>();
		if (a.length > threshold)
			parallelQuicksort(a, 0, a.length - 1, true);
		else
			parallelQuicksort(a, 0, a.length - 1, false);
	}

	public static void parallelQuicksort(int[] a, int leftIndex,
			int rightIndex, boolean parallel) {
		if (!parallel) {
			quicksort(a, leftIndex, rightIndex);
		} else {

			Thread lThread, rThread;

			int i = partition(a, leftIndex, rightIndex);
			int[] left = Arrays.copyOfRange(a, leftIndex, i);
			int[] right = Arrays.copyOfRange(a, i, rightIndex + 1);

			QuickSortWorker leftWorker, rightWorker;

			if (left.length > threshold) {
				leftWorker = new QuickSortWorker(left, 0, left.length - 1, true);
			} else {
				leftWorker = new QuickSortWorker(left, 0, left.length - 1,
						false);
			}
			if (right.length > threshold) {
				rightWorker = new QuickSortWorker(right, 0, right.length - 1,
						true);
			} else {
				rightWorker = new QuickSortWorker(right, 0, right.length - 1,
						false);
			}
			lThread = new Thread(leftWorker);
			rThread = new Thread(rightWorker);

			threads.add(lThread);
			threads.add(rThread);
			lThread.start();
			rThread.start();

			try {
				lThread.join();
				rThread.join();
			} catch (InterruptedException ie) {
			}

			for (int j = leftIndex; j < i; j++) {
				a[j] = leftWorker.getA()[j - leftIndex];
			}
			for (int j = i; j <= rightIndex; j++) {
				a[j] = rightWorker.getA()[j - i];
			}
		}
	}

	public static int partition(int x[], int leftIndex, int rightIndex) {
		int pivot, i, j, help;
		pivot = x[rightIndex];
		i = leftIndex;
		j = rightIndex - 1;
		while (i <= j) {
			if (x[i] > pivot) {
				help = x[i];
				x[i] = x[j];
				x[j] = help;
				j--;
			} else
				i++;
		}
		help = x[i];
		x[i] = x[rightIndex];
		x[rightIndex] = help;

		return i;
	}

	public static int getThreshold() {
		return threshold;
	}

	public static void setThreshold(int threshold) {
		QuickSort.threshold = threshold;
	}
	
	public static int getNumberOfThreads() {
		if(threads != null) {
			return threads.size();
		} else {
			return 0;
		}
	}
}
